/**
 * 双向链表
 * 和普通链表的区别在于
 * 在链表中，一个节点只有链向下一个节点的链接
 * 而在双向链表中，链接是双向的：
 * 一个链向下一个元素，另一个链向前一个元素
 */

//=================================================
//
//                  node
//  ______     ______________         ______ 
// |      |   |    |    |    |->     |      |
// | head |-> |prev|item|next|  ...  | tail |
// |______| <-|____|____|____|     <-|______|
//
//
//=================================================

function DoublyLinkedList(){
  var Node = function(element){
    this.element = element;
    this.prev = null;
    this.next = null;
  }

  var length = 0;
  var head = null;
  var tail = null;

  this.append = function(element){
    var node = new Node(element);

    if(head === null){
      head = node;
      tail = node;
    } else {
      var current = head;
      while(current.next){
        current = current.next;
      }
      current.next = node;
      node.prev = current;
    }
    return ++length;
  }

  this.insert = function(position, element) {
    if(position < length && position > -1){

      var node = new Node(element);
      var current = head;
      var previous = null;
      var index = 0;

      if(position === 0){ // 在第一项添加
        
        if(!head){
          head = node;
          tail = node;
        } else {
          node.next = current;
          current.prev = node;
          head = node;
        }
      } else if(position === length){ // 最后一项
        current = tail;
        current.next = node;
        node.prev = current;
        tail = node;
      } else {
        while(index++ < position){
          previous = current;
          current = current.next;
        }
        node.next = current;
        previous.next = node;

        current.prev = node;
        node.prev = previous;
      }
      return ++length;
    } else {
      return false;
    }
  }

  this.removeAt = function(position){
    if(position < 0 || position >= length){
      return null;
    }
    var current = head;
    var previous = null;
    var index = 0;
    if(position === 0){
      head = current.next;

      // 如果只有一项，更新tail
      if(length === 1){
        tail = null;
      } else {
        head.prev = null;
      }
    } else if(position === length - 1){
      current = tail;
      tail = current.prev;
      tail.next = null;
    } else {
      while(index++ < position){
        previous = current;
        current = current.next;
      }
      previous.next = current.next;
      current.next.prev = previous;
    }
    length--;
    return current.element;
  }

  this.indexOf = function(element){
    var current = head;
    var i = 0;
    while(current.next){
      if(current.element === element){
        return i;
      }
      current = current.next;
      i++;
    }
    return -1;
  }

  this.remove = function(element){
    return this.removeAt(this.indexOf(element));
  }

  this.size = function(){
    return length;
  }

  this.isEmpty = function(){
    return length === 0;
  }

  this.getHead = function(){
    return head;
  }

  this.getTail = function(){
    return tail;
  }
}